package scenic.study.arithmetic.math;

import org.apache.log4j.Logger;
import org.junit.Test;

import java.io.IOException;
import java.io.StreamTokenizer;
import java.io.StringReader;
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.util.*;

import scenic.MyLogger;
import scenic.chart.ShowSimpleXYChart;
import scenic.study.arithmetic.util.StdOut;
import scenic.study.arithmetic.util.StdRandom;
import scenic.study.arithmetic.util.Stopwatch;

import javax.script.ScriptEngine;
import javax.script.ScriptEngineManager;
import javax.script.ScriptException;

/**
 * Created by scenic on 16/7/3.
 * mathematical
 * 经典的数学问题
 */
public class MathModel {

    static Logger logger = MyLogger.get(MathModel.class);

    //牛顿迭代法计算平方根
    @Test
    public void testCalcSqrtValue() {
        double t = 9;
        while (Math.abs(t - 9.0 / t) > 0.001) {
            t = (9.0 / t + t) / 2.0;
        }
        logger.debug("value is " + t);


        int sum = 0;
        for (int i = 1; i < 1000; i++) {
            for (int j = 0; j < i; j++) {
                sum++;
            }
        }
        logger.debug("sum is " + sum);

        sum = 0;

        for (int i = 1; i < 1000; i = i * 2) {
            for (int j = 0; j < 1000; j++) {
                sum++;
            }
        }
        logger.debug("sum is " + sum);

        logger.debug('a' + 'b');
    }

    //获取最大公约数
    public static class GCD {

        /**
         * 获取最大公约数<br>
         * 根据欧几里得定律
         * 计算两个非负整数的最大公约数,p, q
         * 如 q == 0, 则 最大公约数为p
         * 若 r = p % q (将p 除以 q 得到余数 r , 则 p q 的最大公约数是 q和r的最大公约数)
         *
         * @param p
         * @param q
         * @return
         */
        public int gcd(int p, int q) {

            if (q == 0) {
                return p;
            }

            int r = p % q;

            return gcd(q, r);
        }

        public int gcd(int... value) {
            int result = value[0];
            for (int i = 1; i < value.length; i++) {
                result = gcd(result, value[i]);
            }
            return result;
        }


        @Test
        public void testGcd() {

            int gcd = gcd(240, 18);
            System.out.println(gcd);
        }


    }

    //判断一个数是否是素数
    public static class PrimeNumber {
        /**
         * 判断一个数是否是素数
         * 定义 //http://baike.baidu.com/link?url=SMygzuRthXeTRFPhZoiG7gVKGjXWu_wbYqiKmvwbrHiQD5DPeVsNCrphXzCp5_ZGYMzjr16cmWCL1SJC7VhTX8aS1BX8J1OdaTrd_wTmet5-fBz89fFLibgWaNRHH0EouVy5kkRAohbcTQ6qQn0HY99DMVisVVrqfEAoeUExQbq
         *
         * @param N
         * @return
         */
        public static boolean isPrimeNumber(int N) {

            //TODO the terminal case is i * i < N not i < N
            for (int i = 2; i * i < N; i++) {
                if (N % i == 0) {
                    return false;
                }
            }
            return true;
        }

        @Test
        public void testIsPrimeNumber() {
            logger.info(isPrimeNumber(113));
        }
    }

    //print         1	2	3	5	8	13	21	34	55	89	144	233	377	610	987	1597	2584
    public static class Sequence {
        @Test
        public void test2() {
            recursive(1, 1, 0);
            System.out.println();
            noRecursive(1, 1);
        }

        private void noRecursive(int next, int last) {
            for (int i = 0; i < 15; i++) {
                System.out.print(next + "\t");
                next = next + last;
                last = next - last;
            }
        }

        private void recursive(int next, int last, int time) {
            System.out.print(next + "\t");
            if (time > 15) {
                return;
            }
            recursive(next + last, next, time + 1);
        }

    }

    //二进制转化
    public static class ToBinaryString {


        public static BinaryChangeExecute default1 = (value) -> {
            String s = "";
            for (int i = value; i > 0; i = i / 2) {
                s = (i % 2) + s;
            }
            return s;
        };

        public static BinaryChangeExecute default2 = N -> {
            Stack<Integer> stack = new Stack();
            while (N > 0) {
                stack.push(N % 2);
                N = N / 2;
            }

            StringBuffer sb = new StringBuffer();
            while (stack.size() > 0) {
                sb.append(stack.pop());
            }

            return sb.toString();
        };


        private BinaryChangeExecute execute;

        public ToBinaryString(BinaryChangeExecute execute) {
            this.execute = execute;
        }

        public String toBinary(int value) {
            return execute.toBinary(value);
        }


        @Test
        public void test() {
            logger.debug(function1(15));
        }

        private String function1(int n) {
            return Integer.toBinaryString(n);
        }


        interface BinaryChangeExecute {
            String toBinary(int value);
        }


    }

    //calc log2N
    public static class CalcLog {
        @Test
        public void test() {
            logger.debug(lg(8999));
        }

        private int lg(int N) {
            int b = 2;
            int value = b;
            for (int i = 2; ; i++) {
                value = value * b;
                if (value > N) {
                    return i - 1;
                }
            }
        }
    }

    public static class Fibonacci {
        Map<Integer, Double> map = new HashMap<>();

        private Double F(int n) {
            if (n == 0) {
                return 0d;
            }
            if (n == 1) {
                return 1d;
            }
            double value;

            if (false) {
                if (map.containsKey(n)) {
                    value = map.get(n);
                } else {
                    value = F(n - 1) + F(n - 2);
                    map.put(n, value);
                }
            } else {
                value = F(n - 1) + F(n - 2);
            }

            return value;
        }

        @Test
        public void test() {
            logger.debug(F(30));
            for (int i = 0; i < 200; i++) {
                logger.debug(i + "  " +  F(i) );
            }

        }

    }

    public static class BinarySearch {

        private int rank(int key, int[] dataArray) {
            int low = 0;
            int high = dataArray.length - 1;
            while (low <= high) {
                int mid = (high + low) / 2;
                int midValue = dataArray[mid];
                if (key < midValue) high = mid - 1;
                else if (key > midValue) low = mid + 1;
                else return mid;
            }
            return -1;
        }


        @Test
        public void testBinarySearch() {
            int array[] = {10, 11, 12, 13, 14, 15, 16, 17, 110};
            Arrays.sort(array);
            logger.debug(rank(12, array));
        }
    }


    /**
     * calculate string ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )
     */
    public static class CalcStringExpression {


        private Map<String, OperatorCalculatorDefine> binaryOperatorMap = new HashMap<>();

        public CalcStringExpression() {
            //+，-，*，/，%，<，>，>=，<=，==，！=，<<，>>，&，^，|，&&，||，=
            binaryOperatorMap.put("+", (d1, d2) -> (d1 + d2));
            binaryOperatorMap.put("-", (d1, d2) -> (d1 - d2));
            binaryOperatorMap.put("*", (d1, d2) -> (d1 * d2));
            binaryOperatorMap.put("/", (d1, d2) -> (d1 / d2));
            binaryOperatorMap.put("%", (d1, d2) -> (d1 % d2));
        }


        /**
         * 中序表达式转化成后序表达式
         * 中                ->          前
         * 2*3/(2-1)+3*(4-1) ->  +/*23-21*3-41
         * 中                ->          后
         * 2*3/(2-1)+3*(4-1) ->  23*21-/341-*+
         */
        public String infixToPostfix(String infix) {

            StringBuffer sb = new StringBuffer();
            Stack<String> stack = new Stack<>();

            OnExpressionParseListener listener = new OnExpressionParseListener() {
                StringBuffer postfixBuffer = sb;
                Stack<String> stackNew = stack;

                @Override
                public void onParse(String parseStr, Double parseNumber) {
                    if (parseStr == null) {
                        String tmp = (parseNumber.doubleValue() - parseNumber.intValue()) < 0.0000001 ? parseNumber.intValue() + "" : parseNumber.doubleValue() + "";
                        postfixBuffer.append(tmp);
                        postfixBuffer.append(" ");


                    } else if (parseStr.equals("(")) {
                        stackNew.push(parseStr);
                    } else if (parseStr.equals(")")) {
                        while (!stackNew.isEmpty() && !stackNew.peek().equals("(")) {
                            postfixBuffer.append(stackNew.pop());
                            postfixBuffer.append(" ");
                        }
                        stackNew.pop();
                    } else {
                        if (isBinaryOperator(parseStr) || isSingleOperator(parseStr)) {
                            while (
                                    !stackNew.isEmpty() &&
                                            (isSingleOperator(stackNew.peek()) || isBinaryOperator(stackNew.peek())) &&
                                            optLevel(stackNew.peek()) >= optLevel(parseStr)


                                    ) {
                                //优先级高的操作符比低的更靠近栈顶
                                postfixBuffer.append(stackNew.pop());
                                postfixBuffer.append(" ");
                            }
                            stackNew.push(parseStr);
                        }
                    }

                    logger.debug("stackNew " + stackNew);
                    logger.debug("postfixBuffer " + postfixBuffer.toString());
                    logger.debug("             -------             ");
                }
            };

            parseStringExpression(infix, listener);

            while (!stack.isEmpty()) {
                sb.append(stack.pop());
                sb.append(" ");
            }

            return sb.toString();
        }

        public double evaluatePostfix(String postfix) {
            logger.debug("postfix is " + postfix);
            Stack<Double> stack = new Stack<>();

            parseStringExpression(postfix, new OnExpressionParseListener() {
                Stack<Double> stackTmp = stack;

                @Override
                public void onParse(String parseStr, Double parseNumber) {

                    if (parseStr == null) {
                        stackTmp.push(parseNumber);
                    } else {
                        if (isBinaryOperator(parseStr)) {
                            if (stack.size() < 2) {
                                throw new CalcException("parse error may be you need replace the (- a) to (-a) int the expression");
                            }

                            Double p1 = stackTmp.pop();
                            Double p2 = stackTmp.pop();
                            stackTmp.push(calculateTwoValue(p2, parseStr, p1));
                        } else if (isSingleOperator(parseStr)) {
                            stackTmp.push(calculateSingleValue(stackTmp.pop(), parseStr));
                        } else {
                            throw new CalcException("unKnow this case");
                        }
                    }
                    logger.debug("stack " + stackTmp);
                }
            });

            if (stack.size() != 1) {
                throw new CalcException("parse error may be you need replace the 'a -b' to 'a - b'  int the expression");
            }

            return stack.pop();
        }

        /**
         * 计算中序表达式
         *
         * @param expression
         * @return
         */
        public double evaluateInfix(String expression) {
            Stack<String> stackOps = new Stack<>();
            Stack<Double> stackNumbers = new Stack<>();
            logger.debug("expression is " + expression);
            parseStringExpression(expression, new MyOnExpressionParseListener(stackNumbers, stackOps));
            logger.debug("经过去括号运算结果为：");
            logger.debug(stackOps);
            logger.debug(stackNumbers);
            System.out.println();

            if (stackNumbers.size() == 1 && stackOps.size() == 0) {
                //finish the calculate in ()
                return stackNumbers.pop();
            } else {
                // in this case the calculate just like a + b + c not a + ( b + c )
                Stack<Double> stackNumNew = new Stack<>();
                Stack<String> stackOpsNew = new Stack<>();

                stackNumNew.push(stackNumbers.pop());

                while (!stackOps.isEmpty()) {
                    String ops = stackOps.pop();

                    if (isBinaryOperator(ops)) {
                        if (stackNumbers.size() == 0) {
                            throw new CalcException("parse error may be you need replace the '(- b)' to '(-b)' int the expression: " + expression);
                        }

                        stackNumNew.push(stackNumbers.pop());

                        if (optLevel(ops) > 0) {
                            //先根据优先级来计算
                            double tmpResult = calculateTwoValue(stackNumNew.pop(), ops, stackNumNew.pop());
                            stackNumNew.push(tmpResult);
                        } else {
                            //低优先级的先不计算，直接压栈
                            stackOpsNew.push(ops);
                        }
                    } else {
                        //单目运算 like that [sin]  [3.0]
                        stackNumNew.push(calculateSingleValue(stackNumNew.pop(), ops));
                    }
                }

                logger.debug("经过优先级计算之后的结果");
                logger.debug("操作符堆栈: " + stackOpsNew + "\t" + "数据堆栈: " + stackNumNew);
                System.out.println();

                //此刻要进行检测，有可能存在解析出错的问题， 比如 1 -2 可能会解析成 【】【1 ，-2】而不是 【-】【1，2】
                if (stackNumbers.size() != 0) {
                    throw new CalcException("parse error may be you need replace the 'a -b' to 'a - b' int the expression: " + expression);
                }
                while (stackOpsNew.size() != 0) {
                    stackNumNew.push(calculateTwoValue(stackNumNew.pop(), stackOpsNew.pop(), stackNumNew.pop()));
                }

                if (stackNumNew.size() == 1 && stackOpsNew.size() == 0) {
                    return stackNumNew.pop();
                }
            }

            throw new CalcException("UNKnow some error occur");
        }

        /**
         * 双目运算符
         *
         * @param ops
         * @return
         */
        private boolean isBinaryOperator(String ops) {
            return binaryOperatorMap.containsKey(ops);
        }

        private boolean isSingleOperator(String ops) {
            Method methods[] = Math.class.getMethods();
            for (Method m :
                    methods) {
                if (m.getName().equals(ops)) {
                    return true;
                }
            }
            return false;
        }


        private double calculateTwoValue(Double value1, String operator, Double value2) {
            double result;
            switch (operator) {
                case "+":
                    result = value1 + value2;
                    break;
                case "-":
                    result = value1 - value2;
                    break;
                case "*":
                    result = value1 * value2;
                    break;
                case "/":
                    result = value1 / value2;
                    break;
                default:
//
                    result = binaryOperatorMap.get(operator).calc(value1, value2);
            }

            return result;
        }

        private int optLevel(String opt) {
            Map<String, Integer> levelMapping = new HashMap<>();
            levelMapping.put("+", 0);
            levelMapping.put("-", 0);
            levelMapping.put("*", 1);
            levelMapping.put("/", 1);
            levelMapping.put("%", 1);

            if (levelMapping.containsKey(opt)) {
                return levelMapping.get(opt);
            } else {
                if (isSingleOperator(opt)) {
                    return 3;
                } else {
                    throw new CalcException("not support this case " + opt);
                }
            }

        }

        private double calculateSingleValue(Double value1, String operator) {
            try {
                Method method = Math.class.getMethod(operator, double.class);
                return (double) method.invoke(null, value1);
            } catch (NoSuchMethodException e) {
                e.printStackTrace();
            } catch (InvocationTargetException e) {
                e.printStackTrace();
            } catch (IllegalAccessException e) {
                e.printStackTrace();
            }
            throw new CalcException("need adjust the calculate method " + value1 + "   " + operator);
        }

        private void parseStringExpression(String expression, OnExpressionParseListener listener) {
            StreamTokenizer streamTokenizer = new StreamTokenizer(new StringReader(expression));
            streamTokenizer.ordinaryChar('/');
            try {
                while (streamTokenizer.nextToken() != StreamTokenizer.TT_EOF) {
                    int ttype = streamTokenizer.ttype;
                    String sval = streamTokenizer.sval;
                    double nval = streamTokenizer.nval;
                    String operation = null;
                    double number = Double.NaN;
                    if (ttype == StreamTokenizer.TT_NUMBER) {
                        number = nval;
                    } else if (ttype == StreamTokenizer.TT_WORD) {
                        operation = sval;
                    } else {
                        operation = new String(new char[]{(char) ttype}).intern();
                    }

                    if (listener != null) {
                        listener.onParse(operation, number);
                    }
                }
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

        public interface OnExpressionParseListener {
            void onParse(String parseStr, Double parseNumber);
        }

        public interface OperatorCalculatorDefine {
            double calc(double d1, double d2);
        }

        public static class CalcException extends RuntimeException {
            public CalcException(String message) {
                super(message);
            }
        }

        class MyOnExpressionParseListener implements OnExpressionParseListener {
            private Stack<Double> stackNumbers;
            private Stack<String> stackOps;

            MyOnExpressionParseListener(Stack<Double> stackNumbers, Stack<String> stackOps) {
                this.stackNumbers = stackNumbers;
                this.stackOps = stackOps;
            }

            @Override
            public void onParse(String parsedStr, Double parsedNumber) {
                if (parsedStr == null) {
                    //add number
                    stackNumbers.push(parsedNumber);
                    logger.debug("数字入栈");
                    logger.debug("操作符堆栈:\t" + stackOps);
                    logger.debug("数据堆栈:\t" + stackNumbers);
                    System.out.println();
                } else if (parsedStr.equals("(")) {

                } else if (parsedStr.equals(")")) {
                    //有可能最后一个大括号多一个，不对等，所以要加入这个判断
                    if (stackOps.size() > 0) {
                        String ops = stackOps.pop();
                        double result = stackNumbers.pop();
                        if (isBinaryOperator(ops)) {
                            result = calculateTwoValue(stackNumbers.pop(), ops, result);
                        } else {
                            result = calculateSingleValue(result, ops);
                        }

                        // push the result of calculator
                        stackNumbers.push(result);

                        logger.debug("遇到括号出栈计算后入栈");
                        logger.debug("操作符堆栈:\t" + stackOps);
                        logger.debug("数据堆栈:\t" + stackNumbers);
                        System.out.println();
                    }
                } else {
                    //add operator
                    stackOps.push(parsedStr);
                    logger.debug("操作符入栈");
                    logger.debug("操作符堆栈:\t" + stackOps);
                    logger.debug("数据堆栈:\t" + stackNumbers);
                    System.out.println();
                }
            }
        }

        public static void main(String args[]) throws ScriptException {

//            String expression = "( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )";
            String expression = "1 - 1";
            logger.debug(new CalcStringExpression().evaluateInfix(expression));


            ScriptEngineManager manager = new ScriptEngineManager();
            ScriptEngine engine = manager.getEngineByName("JavaScript");
            System.out.println(engine.eval("(1 - (- 1))"));

        }


        ///////////////////////////////add test interface

        void testParseStringExpression(String express, OnExpressionParseListener l) {
            parseStringExpression(express, l);
        }

        boolean testIsSingleOperator(String opt) {
            return isSingleOperator(opt);
        }

    }


    /**
     * 探究算法的效率曲线
     */
    public static class DoublingTest {
        static ExecuteSome threeSumModel = new ThreeSumModel();
        static ExecuteSome threeSumFast = new ThreeSumFast();
        static  ExecuteSome nLogN = new NLnNModel();
        static  ExecuteSome nLogN2 = new NLnNMode2();
        static ExecuteSome testModel = threeSumModel;
        static {
            testModel = nLogN ;
            testModel = threeSumFast;
        }

        DoublingTest(){
            testModel = nLogN2;
        }

        public interface ExecuteSome {
            int execute(int a[]);
        }

        private static void doSomething(){
            try {
                Thread.sleep(0);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        static class ThreeSumModel implements ExecuteSome {

            public int execute(int a[]) {
                int N = a.length;
                int cnt = 0;
                for (int i = 0; i < N; i++) {
                    for (int j = i + 1; j < N; j++) {
                        for (int k = j + 1; k < N; k++) {
                            if (a[i] + a[j] + a[k] == 0) {
                                cnt++;
                                try {
                                    Thread.sleep(0);
                                } catch (InterruptedException e) {
                                    e.printStackTrace();
                                }
                            }
                        }
                    }
                }
                return cnt;
            }

        }

        static class ThreeSumFast implements ExecuteSome {

            @Override
            public int execute(int[] a) {
                Arrays.sort(a);
                int N = a.length;
                int cnt = 0;
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < N; j++) {
                        if(Arrays.binarySearch(a,-(a[i] + a[j])) > i) {
                            cnt++;
                        }
                    }
                }
                return cnt;
            }
        }

        static class NLnNModel implements ExecuteSome {

            @Override
            public int execute(int[] a) {
                int N = a.length;
                int cont = 0;
                for (int i = N; i > 0 ; i/=2) {
                    for (int j = 0; j < N; j++) {
                        doSomething();
                    }
                }
                return cont;
            }
        }

        static class NLnNMode2 implements ExecuteSome {

            @Override
            public int execute(int[] a) {
                int N = a.length;
                int cont = 0;
                for (int i = 1; i < N ; i*=2) {
                    for (int j = 0; j < i; j++) {
                        doSomething();
                    }
                }
                return cont;
            }
        }

        public double timeTrial(int N) {
            int max = 1000000;
            int a[] = new int[N];
            for (int i = 0; i < N; i++) {
                a[i] = StdRandom.uniform(-max, max);
            }
            Stopwatch timer = new Stopwatch();
            testModel.execute(a);

            return timer.elapsedTime();
        }

        public static void main(String args[]) {

            ShowSimpleXYChart chart = new ShowSimpleXYChart("scenic");
            Map  map = Collections.synchronizedMap(new LinkedHashMap<Number, Number>()) ;
            DoublingTest doublingTest = new DoublingTest();

            System.out.println(DoublingTest.testModel);
            for (int i = 250; true; i +=i) {
                double time = doublingTest.timeTrial(i);
                StdOut.printf("%7d  %5.1f\n",i,time);
                map.put( i,time);
                chart.update(map);
            }

        }

    }

}


/*




 */